package com.openess.bigsearch.engine.utils;

import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.Iterator;
import java.util.Set;

/**
 * 模仿java.util.HashMap<K, V>
 * 
 * @author TuTu
 * 
 */
public class HashMap<K, V> implements Map<K, V> {
	/**
	 * 散列表所基于的数组大小
	 */
	public static final int DEFAULT = 16;

	/**
	 * 在java.util.HashMap中使用的是Map.Entry，而不是使用链表集合，好处在于进一步减少了所需要的空间
	 */
	protected Entry<K, V>[] table;

	/**
	 * 散列表中保存数据的个数
	 */
	protected int size = 0;

	/**
	 * 进行默认的初始化操作
	 */
	public HashMap() {
		this(DEFAULT);
	}

	/**
	 * 指定容量进行初始化操作
	 * 
	 * @param capacity
	 */
	public HashMap(int capacity) {
		// 暂时舍弃泛型，因为不允许创建泛型数组
		table = new Entry[capacity];
	}

	/**
	 * 散列函数，计算散列值，暂时使用最简单的求余法
	 * 
	 * @param key
	 * @return
	 */
	public int hash(int key) {
		// 有的对象的hashcode可能计算出负值，主要是因为超出了int的上限。例如比较长的String类型
		if (key < 0) {
			key = Math.abs(key);
		}
		return key % table.length;
	}

	@Override
	public V put(K key, V value) {
		int hashcode = key.hashCode();
		int hash = hash(hashcode);
		for (Entry<K, V> entry = table[hash]; entry != null; entry = entry.next) {
			K k = entry.key;
			if (k.equals(key)) {
				V oldValue = entry.value;
				entry.value = value;
				return oldValue;
			}
		}
		addEntry(hash, key, value);
		size++;
		return null;
	}

	private void addEntry(int hash, K key, V value) {
		Entry<K, V> e = table[hash];
		table[hash] = new Entry<K, V>(key, value, e);
	}

	/**
	 * 集合中的数据个数
	 * 
	 * @return
	 */
	public int size() {
		return size;
	}

	public V get(Object ob) {
		if (ob == null)
			return null;
		int hash = hash(ob.hashCode());
		for (Entry<K, V> e = table[hash]; e != null; e = e.next) {
			if (e.key.equals(ob))
				return e.value;
		}
		return null;
	}

	@Override
	public V remove(Object ob) {
		if (ob == null)
			return null;
		int hash = hash(ob.hashCode());
		// 使用3个变量：prev, e, next好处是不需要判断头结点的删除
		Entry<K, V> prev = table[hash];
		Entry<K, V> e = prev;
		for (Entry<K, V> next = e.next; e != null;) {
			if (e.key.equals(ob)) {
				if (prev == e)
					table[hash] = next;
				else
					prev.next = next;
				return e.value;
			}
			prev = e;
			e = next;
		}
		return null;
	}

	@Override
	public String toString() {
		String str = "info: the size of HashMap is " + this.size
				+ ", the length of the array is " + this.table.length + ".";
		int i = 0;
		for (Entry<K, V> en : this.table) {
			str += "\n" + i + ": " + en;
			en = en.next;
			for (; en != null; en = en.next)
				str = str + "--" + en.toString();
			i++;
		}
		return str;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public void putAll(Map<? extends K, ? extends V> map) {
		for (Map.Entry<? extends K, ? extends V> e : map.entrySet()) {
			put(e.getKey(), e.getValue());
		}
	}

	@Override
	public Set<Map.Entry<K, V>> entrySet() {
		return new EntrySet();
	}

	@Override
	public Set<K> keySet() {
		return new KeySet();
	}

	class EntrySet extends AbstractSet<Map.Entry<K, V>> {
		@Override
		public Iterator<Map.Entry<K, V>> iterator() {
			return new EntryIterator();
		}

		@Override
		public int size() {
			return size;
		}
	}

	class KeySet extends AbstractSet<K> {
		@Override
		public Iterator<K> iterator() {
			return new KeyIterator();
		}

		@Override
		public int size() {
			return size;
		}
	}

	private class EntryIterator extends HashIterator<Map.Entry<K, V>> {
		@Override
		public Entry<K, V> next() {
			return nextEntry();
		}
	}

	public class KeyIterator extends HashIterator<K> {
		@Override
		public K next() {
			return nextEntry().key;
		}
	}

	public class ValueIterator extends HashIterator<V> {
		@Override
		public V next() {
			return nextEntry().value;
		}
	}

	public abstract class HashIterator<E> implements Iterator<E> {
		/**
		 * 用于记录当前遍历到的table下标位置
		 */
		private int index = 0;
		/**
		 * 指向当前Entry的下一个
		 */
		private Entry<K, V> next;
		/**
		 * 指向当前Entry
		 */
		private Entry<K, V> current;

		public HashIterator() {
			// 取到table中的第一个Entry<K, V>
			while (index < table.length && (next = table[index++]) == null)
				;
		}

		@Override
		public boolean hasNext() {
			return next != null;
		}

		public Entry<K, V> nextEntry() {
			current = next;
			// 取下一个Entry，如果链表到头了，那么遍历下一个table[i]
			next = next.next;
			if (next == null)
				while (index < table.length && (next = table[index++]) == null)
					;
			return current;
		}

		@Override
		// 在java.util中迭代器的remove()并不是在迭代的过程中删除的Entry，而是拿到Entry的key调用集合的remove方法，效率相对低
		public void remove() {
			K key = current.key;
			HashMap.this.remove(key);
		}
	}

	public Collection<V> values() {
		return new Values();
	}

	public class Values extends AbstractCollection<V> {

		@Override
		public Iterator<V> iterator() {
			return new ValueIterator();
		}

		@Override
		public int size() {
			return size;
		}
	}

	@Override
	public boolean containsKey(Object ob) {
		int hash = hash(ob.hashCode());
		for (Entry<K, V> e = table[hash]; e != null; e = e.next) {
			if (e.key.equals(ob))
				return true;
		}
		return false;
	}

	@Override
	public boolean containsValue(Object value) {
		for (int i = 0; i < table.length; i++)
			for (Entry<K, V> e = table[i]; e != null; e = e.next) {
				if (e.value.equals(value))
					return true;
			}
		return false;
	}

	@Override
	public void clear() {
		for (int i = 0; i < table.length; i++)
			table[i] = null;
		size = 0;
	}

	static class Entry<K, V> implements Map.Entry<K, V> {
		private K key;
		private V value;
		private Entry<K, V> next;

		private Entry(K key, V value, Entry<K, V> next) {
			this.key = key;
			this.value = value;
			this.next = next;
		}

		@Override
		public K getKey() {
			return key;
		}

		@Override
		public V getValue() {
			return value;
		}

		@Override
		public V setValue(V value) {
			V oldValue = this.value;
			this.value = value;
			return oldValue;
		}

		@Override
		public boolean equals(Object o) {
			if (o instanceof Map.Entry) {
				Map.Entry entry = ((Map.Entry) o);
				Object key1 = entry.getKey();
				Object key2 = entry.getKey();
				if (key1 != null && key2 != null && key1.equals(key2)) {
					Object value1 = entry.getValue();
					Object value2 = entry.getValue();
					if (value1 != null && value2 != null
							&& value1.equals(value2))
						return true;
				}
			}
			return false;
		}

		@Override
		public String toString() {
			return "<" + key + "," + value + ">";
		}
	}
}
